package com.lg.algorithm.finder;

/**
 * 查找
 */
public class Base {

    /**
     * 二分查找
     *  有序数组中是否有重复的值
     *      返回下标还是数组下标
     *      返回前边的还是后边的
     *  相加除二 可能越界怎么处理
     *
     *  有重复的  返回前边的 下标
     */
    static int binaryFinder(int[] arr,int value) {
        int start = 0;
        int end = arr.length;
        //index  in  [start , end)
        while (start < end){
            /**
             * arr != null !!   yes
             * end - start = 0
             *     空数组
             *     arr[0] 出错
             *     start = end = mid
             *     得 start < end
             *
             * end - start = 1
             *      end = start +1
             *      mid = start
             *          arr[mid] < value
             *          start = mid + 1 = end
             *          上方结论条件可满足
             *
             *          arr[mid] > value
             *          end = mid = start
             *          上方结论条件可满足
             *
             * end - start = 2
             *      end = start + 2
             *      mid = start + 1
             *      mid = end - 2
             */

            int mid = ((end - start) >> 1) + start;
//            int mid = (start + end) / 2;
            if (arr[mid] < value) {
                start = mid + 1;
            } else if (arr[mid] > value) {
                end = mid;
            } else {
                return mid;
            }
        }

        return -1;
    }

    public static void main(String[] args) {

        int [] arr = {1,2,3,4,5};
        System.out.println(binaryFinder(arr,0));
        System.out.println(binaryFinder(arr,7));
        System.out.println(binaryFinder(arr,1));
        System.out.println(binaryFinder(arr,3));
        System.out.println(binaryFinder(arr,5));

        System.out.println("-----上述逻辑找不到 第一个最左边的下标 只能找到中间的-----");
        int [] arr2 = {2,2,2};
        System.out.println(binaryFinder(arr2,2));
    }
}
